package com.markus.code.dfs;

import com.markus.code.top100.LeetCode4;

import java.util.ArrayList;
import java.util.List;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/25 17:32
 * todo: 递增子序列
 */
public class LeetCode_491 {
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> ansList = new ArrayList<>();
        if (nums == null || nums.length <= 1) {
            return ansList;
        }
        List<Integer> path = new ArrayList<>();
        process(nums, 0, Integer.MIN_VALUE,path, ansList);
        return ansList;
    }

    /**
     * 如何判断重复呢？
     * 其实在相同元素的时候，子序列有四种情况
     * 前者未被选择，后者未被选择
     * 前者被选择，后者未被选择
     * 前者未被选择，后者被选择
     * 前者被选择，后者被选择
     *
     * 第二种和第三种情况是重复的，只有当前元素不等于前一个被选择的元素，我们才考虑不选择当前元素
     */
    private void process(int[] nums, int index, int last,List<Integer> path, List<List<Integer>> ansList) {
        if (index == nums.length) {
            if (path.size() >= 2) {
                ansList.add(new ArrayList<>(path));
            }
            return;
        }
        //考虑选择当前元素
        if (nums[index] >= last){
            path.add(nums[index]);
            process(nums,index+1,last,path,ansList);
            path.remove(path.size()-1);
        }
        //只有在当前元素不等于前面的元素时才考虑不选择当前元素
        if (nums[index] != last){
            process(nums,index+1,last,path,ansList);
        }
    }

    private boolean isValid(List<Integer> path) {
        for (int i = 0; i < path.size()-1; i++) {
            if (path.get(i+1) < path.get(i)){
                return false;
            }
        }
        return path.size()>=2;
    }

    public static void main(String[] args) {
        int arr[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
        LeetCode_491 demo = new LeetCode_491();
        List<List<Integer>> lists = demo.findSubsequences(arr);
        for (List<Integer> list : lists) {
            for (Integer i : list) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }
}
